백준 2075번 - N번째 큰 수

문제링크

풀이과정

힙으로 구현해보려고 했다.

max heap으로 구현

max heap으로 모든 수를 heap에 집어넣고 큰 수 부터 pop하면서 n번째로 pop되는 수를 출력하려고 했다.

import heapq

n = int(input())
# array = [list(map(int, input().split())) for _ in range(n)]

heap = []
for _ in range(n):
    for i in list(map(int, input().split())):
        heapq.heappush(heap, -i)

for i in range(n - 1):
    heapq.heappop(heap)

print(-heap[0])

• [I] heap의 크기를 n 으로 제한하면서 n+1번째로 큰 수는 heap에서 빼버리면 메모리를 아낄 수 있겠다.

힙에서 n번째 큰 수를 찾는 것은 불가능하다. 이진탐색 트리 처럼 순서를 보장해주지않는다. 힙은 최대/최솟값에 특화되어있다

min heap

이 문제를 min heap으로 해결할 수 있었다.
새로운 값이 들어오는 값이 가장 작은 값보다 크면 가장 작은 값을 밀어내는 방식으로 값의 갯수를 일정하게 유지할 수 있다.
=> 즉 min heap으로 큰 15개의 값만 유지하는 것이다.

import heapq

n = int(input())
heap = []

for _ in range(n):
    for i in list(map(int, input().split())):
        if len(heap) < n:
            heapq.heappush(heap, i)
        elif i > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, i)

print(heap[0])

관련글

• 힙
• 우선 순위 큐